package Leetcode.图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/9/9 14:25
 * @Description:
 * 给你一个整数 n 和一个二维整数数组 queries。
 *
 * 有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。
 *
 * queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，
 * 你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
 *
 * 返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，
 * 从城市 0 到城市 n - 1 的最短路径的长度。
 *
 * 示例 1：
 *
 * 输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
 *
 * 输出： [3, 2, 1]
 *
 * 新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。
 */

public class 新增道路查询后的最短距离 {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        // 创建一个图，其中每个节点都有一个列表来存储它可以直接到达的节点
        List<Integer>[] graph = new ArrayList[n - 1];
        Arrays.setAll(graph, i -> new ArrayList<>());

        // 初始化图：每个点可以通向下一个节点
        for (int i = 0; i < n - 1; i++) {
            graph[i].add(i + 1);
        }

        // 创建一个数组来存储每个查询的结果
        int[] ans = new int[queries.length];
        // 创建一个数组来记录每个节点是否在当前查询中已经被访问过
        int[] visited = new int[n - 1];

        // 遍历每个查询
        for (int i = 0; i < queries.length; i++) {
            // 将查询中的新边添加到图中
            graph[queries[i][0]].add(queries[i][1]);
            // 使用广度优先搜索（BFS）计算从起点到终点的最短距离
            ans[i] = bfs(i + 1, graph, visited, n);
        }
        // 返回所有查询的结果
        return ans;
    }

    // 使用广度优先搜索计算从起点到终点的最短距离
    private int bfs(int queryIndex, List<Integer>[] graph, int[] visited, int n) {
        // 创建一个列表来存储当前层的节点
        ArrayList<Integer> list = new ArrayList<>();
        // 起始点为0
        list.add(0);

        // 步长初始化为1，代表从起点到当前层的距离
        for (int step = 1; ; step++) {
            // 临时列表存储当前层的节点
            List<Integer> temp = list;
            // 清空列表以存储下一层的节点
            list = new ArrayList<>();

            // 遍历当前层的所有节点
            for (int x : temp) {
                // 遍历当前节点可以到达的所有节点
                for (int y : graph[x]) {
                    // 如果到达了终点，返回当前步长
                    if (y == n - 1) {
                        return step;
                    }
                    // 如果节点在当前查询中没有被访问过，则标记为已访问并添加到下一层
                    if (visited[y] != queryIndex) {
                        visited[y] = queryIndex;
                        list.add(y);
                    }
                }
            }
        }
    }

}
